package class03;

import class02.randoom.GenerateRandomArray;

/**
 * @Auther: xw
 * @Create: 2022/3/4 17:51
 * @Description: 获得某个数组（相邻位置的数不相等）的局部最小值的位置
 */
public class LocalMin {
    public static int getLocalMin(int[] arr){
        if(null == arr || arr.length == 0){
            return -1;
        }
        int length = arr.length;
        if(length == 1){
            return 0;
        }
        if(arr[0] < arr[1]){
            return 0;
        }
        if(arr[length-1] < arr[length-2]){
            return length-1;
        }

        int left =0;
        int right = length -1;
         while(left < right-1){
             int middle = (left + right)/2;
             if(arr[middle] < arr[middle-1] && arr[middle] < arr[middle+1]){
                return middle;
             }else{// 只要左边大于middle，就去左边找
                 if(arr[middle]> arr[middle -1]){
                     right = middle -1 ;
                 }else{
                     left = middle +1;
                 }
             }
         }
         return arr[left] < arr[right] ? left : right;
    }

    /**
     * 得到无序且左右不相等的数组
     * @param maxLength
     * @param maxValue
     * @return
     */
    public static int[] getNotEqualsArray(int maxLength,int maxValue){

        int length = (int)(Math.random() * maxLength );
        int[] arr = new int[length];
        if(length > 0){
            arr[0] = (int)(Math.random() * maxValue);
            for (int i = 1; i < length; i++) {
                do{
                    arr[i] = (int)(Math.random() * maxValue);
                }while (arr[i] == arr[i-1]);
            }}
        return arr;
    }

    /**
     * 检查是否是局部最小
     * @param arr
     * @param minIndex
     * @return
     */
    public  static  boolean check(int[] arr, int minIndex){
        if(0 == arr.length){
            return minIndex == -1;
        }
        int left = minIndex -1;
        int right = minIndex + 1;
        boolean leftBigger = left  >= 0  ? arr[left] > arr[minIndex] : true;
        boolean rightBigger = right  < arr.length  ? arr[right] > arr[minIndex] : true;
        return leftBigger && rightBigger;
    }

    public static void main(String[] args) {
        int maxLength = 10;
        int maxValue = 100;
        int times = 10000;

        System.out.println("测试开始");
        for (int i = 0; i < times; i++) {
            int[] arr = getNotEqualsArray(maxLength, maxValue);
            int ans = getLocalMin(arr);
            if (!check(arr, ans)) {
                GenerateRandomArray.printArray(arr);
                System.out.println(ans);
                break;
            }
        }
        System.out.println("测试结束");

    }
}
